//
//  main.swift
//  02-选择排序
//
//  Created by XFB on 2020/4/3.
//  Copyright © 2020 XFB. All rights reserved.
//

import Foundation

/**
 选择排序：扫描挑选最大值或者最小值
 
 1、从序列中找出最小的那个元素，然后与最开始的元素交换位置
    执行完一轮后，最开始那个元素就是最小的元素
 2、忽略步骤1中曾经找到的最小元素，重复执行步骤1
 
 选择排序的交换次数远少于冒泡排序，平均性能优于冒泡排序
 最好、最坏、平均时间复杂度 O(n^2)，空间复杂度 O(1) 属于稳定排序
 */

func selectionSorted(_ nums: [Int]) {
    var array = nums
    print(array)

    // 扫描多少次
    for i in 0 ..< array.count - 1  {
        // 默认第0个位置是最小值
        var minIndex = i
        for j in i ..< array.count {
            if array[minIndex] > array[j] {
                minIndex = j
            }
        }
//        array.swapAt(i, minIndex)
        let temp = array[minIndex]
        array[minIndex] = array[i]
        array[i] = temp
    }
    
    // 打印是否已经排好序
    print(isAscOrder(array: array))
}

//let nums = tailOrderRandomArray(min: 1, max: 2000, orderCount: 1500)
let nums = RandomArray(min: 0, max: 1000, length: 10)
//let nums = ascOrderRandomArray(min: 10, max: 100)
//print(isAscOrder(array: nums))

// 冒泡排序 - 优化2
let time = executeTime {
    selectionSorted(nums)
}
print("选择排序耗时：\(time)秒")
